Continuous tone images do not print well on most printing devices, so the image is usually printed as pattern of dots based on a grid. The grid consists of an array of halftone cells, each of which represents one section of continuous tone in the original image. When reproducing a halftoned image in this way using a digital recording device, a halftone cell consists of a plurality of device pixels. A portion of display pixels of each halftone cell are turned black to form dots relatively larger or smaller to represent darker or lighter portions of the original continuous tone image. A dark halftone cell will have most of its pixels turned black while a light halftone cell will have most of its pixels turned white. A complete grid of the original image is composed of many such halftone cells, each of which has an independent density of displayed pixels and therefore a different apparent darkness when viewed from a distance.
A common prior art method of selecting which dots in each halftone cell to turn black works as follows: For a given half-tone cell, the original image is sampled at each display pixel location in said halftone cell to obtain a gray value. This gray value is represented digitally as a number in a fixed range, typically 0 to 255. The gray value is then compared to a threshold value in the same range and the display pixel is turned white if the image gray value is greater than the threshold value; otherwise it remains black. The threshold values, in turn, are supplied by means of a threshold array which contains a separate threshold value for each pixel in the halftone cell, and are computed prior to processing the image. This process is carried out for each halftone cell of the image.
This method works best when the same threshold array can be used for all halftone cells in the image. One advantage is that only one threshold array needs to be calculated and stored for the entire image. Another advantage is that a gray area of a given intensity will produce dots of the same size and shape no matter where it occurs in the image. However, in order for this to work, the set of display pixels corresponding to each halftone cell in the image must be exactly the same size and shape as the set of display pixels corresponding to any other halftone cell. This requirement is most often met by requiring the halftone cells to be parallelograms whose corners all fall exactly on integral coordinates in display pixel space. U.S. Pat. No. 4,185,304, incorporated herein by reference, shows one embodiment of this method.
One problem with the above method is that the number of different halftone screens that can be reproduced is limited by the requirement that the corners of the halftone cells must fall on integer coordinates in display pixel space. For example, the screens rotated through 15.degree. or 75.degree. commonly used in color printing cannot be accurately reproduced. This shortcoming is addressed in a first copending U.S. patent application Ser. No. 434,924, incorporated herein by reference, filed Nov. 8, 1989 by the same inventor and assigned to the same assignee as this invention (hereafter called the first copending application). Where it is shown how a threshold array that consists of multiple halftone cells can be used to increase the number of available halftone screens to the point where any arbitrary screen can be approximated to within adequate tolerances.
When the threshold array contains more than one ideal cell, it is desirable that this fact be invisible to the user. This means that all the halftone dots produced by one copy of the threshold array, for a given gray level, must be of the same size and equally spaced.
Unfortunately the multiple halftone cells in such a threshold array generally have to be of differing shapes and sizes when those halftone cells are represented by display pixels. This means that the dots produced by the different halftone cells may also be of different shapes and sizes even when they represent the same gray value. Depending on the degree of the differences in the size and shape of halftone dots, these differences may or may not be visible to the human eye. When they are visible, one sees a mottled variation in gray intensity in the form of repeating spots o; bands where the original image contained only a constant gray. Such patterns do not faithfully reproduce the original image and are thus undesirable.
The following terms are defined for clarity. An ideal halftone cell, or ideal cell for short, will be a halftone cell such as the ones discussed above: an element of the halftone grid consisting of an area bounded by a rotated square or a parallelogram. In contrast, a digital halftone cell, or digital cell for short, will be a set of pixels used to approximate an ideal halftone cell. Thus each digital halftone cell is associated with a specific ideal halftone cell that it approximates. Also, in keeping with the above-mentioned copending U.S. patent application Ser. No. 434,924, incorporated herein by reference, a threshold array that consists of multiple halftone cells will be referred to as a "supertile".
In the prior art method of generating a supertile as disclosed in the copending application a digital halftone cell consists of all the pixels in the supertile whose geometric centers fall within the associated ideal cell. This method creates digital halftone cells of satisfactory consistency for certain halftone screens, but for other screens, an unsatisfactory variation in digital cell size results. These variations occur because, although each ideal cell has the same shape, its placement with respect to the pixel grid varies by fractional amounts of pixels. Thereby, in some cases, more pixel centers fall inside an ideal cell and in other cases fewer pixels centers fall inside an ideal cell. The resulting variations in the size of the digital halftone cells causes corresponding variations in the size of halftone dots when certain values of gray are reproduced. This is called the unequal cell size problem, addressed in a second copending U.S. patent application Ser. No. 07/652,927, filed Feb. 8, 1991, by the same inventor and assigned to the same assignee as this invention, incorporated herein by reference.
Another type of error is caused at certain gray levels where a given black or a white halftone dot crosses the boundaries of its digital halftone cell and overlaps pixels on neighboring digital cells. A single black or white halftone dot might be split into two or more pieces, each piece residing in a separate digital halftone cell, as shown in FIG. 1. Because a digital halftone cell 130A-F may be asymmetric relative to the corresponding ideal halftone cell 120A-F, the various pieces of a halftone dot 70A-F in an ideal cell 120A-F may also get pixels allocated asymmetrically. When the digital halftone cells 130A-F are put together and whole halftone dots 70A-F are formed, the pieces that are used to form a given halftone dot may be too small or too large relative to a predetermined expected size even though the correct total halftone dot pixels within each digital cell.
For example each of the digital cells 130A-F of FIG. 1 are assigned ten black pixels (shown cross hatched); the remaining pixels are white. The black pixels create dots 70A-F. Dot 70A is the correct predetermined size. It includes ten black pixels, nine pixels are primarily within digital cell 130A and one is primarily in digital cell 130B. However, dot 70B includes only eight black pixels, one of which is primarily in digital cell 130C. Dot 70E includes twelve black pixels of which nine are primarily in cell 130E, two are primarily in digital cell 130B and one is primarily in digital cell 130F. This problem is called the multi-cell dot (MCD) problem. It is a principal object of this invention to correct the above multi-cell dot problem.